package lanQiaoBei.tree;
/*
* 二叉树的递归套路
* 思想：当前节点在保证可以向左右节点要信息的情况下的递归
* */
public class TreeRecSkill {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node1.setRight(node2);
//        node1.setLeft(node8);
//        node2.setRight(node7);
        node3.setLeft(node1);
        node3.setRight(node4);
        node4.setRight(node5);
//        node4.setLeft(node6);
        System.out.println(isBalanceTree(node3).isBalanced);
        System.out.println(isBST(node3).isBST);
    }
    /*递归套路判断是否为搜索二叉树*/
    static class R1{
        private boolean isBST;
        private int min;
        private int max;

        public R1(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }
    public static R1 isBST(TreeNode root){
           if(root==null){
               return null;
           }
        R1 lr = isBST(root.getLeft());
        R1 rr = isBST(root.getRight());
        int min=root.getVal();
        int max=root.getVal();
        boolean isBST=true;
        if(lr!=null){
            min=Math.min(min, lr.min);
            max=Math.max(max, lr.max);
        }
        if(rr!=null){
            max=Math.max(max, rr.max);
            min=Math.min(min,rr.min);
        }
        if(lr!=null&&(!lr.isBST||root.getVal()< lr.min)){
            isBST=false;
        }
        if(rr!=null&&(!rr.isBST||root.getVal()>rr.max)){
            isBST=false;
        }
        return new R1(isBST,min,max);
    }
    /*递归套路判断是否为平衡二叉树*/
    static class R{
        private int height;
        private boolean isBalanced;
        R(boolean isBalanced,int height){
            this.isBalanced=isBalanced;
            this.height=height;
        }
        public int getHeight() {
            return height;
        }

        public boolean isBalanced() {
            return isBalanced;
        }
    }
    public static R isBalanceTree(TreeNode root){
           if(root==null){
               return new R(true,0);
           }
        R lr = isBalanceTree(root.getLeft());
        R rr = isBalanceTree(root.getRight());
        int height=0;
        boolean isBalanced;
        height=Math.max(lr.height,rr.height)+1;
        isBalanced=lr.isBalanced&&rr.isBalanced&&(Math.abs(lr.height-rr.height)<=1)?true:false;
        return new R(isBalanced,height);
    }
}
